package leet;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 928. Minimize Malware Spread II
 * 
 * @author zhujunbing
 * @date 2019年4月23日
 */
public class Leet0928 {

	public static void main(String[] args) {
		Leet0928 leet928 = new Leet0928();

		int[][] graph = { { 1, 1, 0, 0 }, { 1, 1, 1, 0 }, { 0, 1, 1, 1 }, { 0, 0, 1, 1 } };
		int[] initial = { 0, 1 };
		int minMalwareSpread = leet928.minMalwareSpread(graph, initial);

		System.out.println(minMalwareSpread);// 1
	}

	/**
	 * 
	 * 删除传染源，能够减少最多的传染，需要知道只有该传染源能传染的点的数量， 显然有多个传染源能传染到的点切断了一个传染源也没用
	 * 
	 * 从一个传染源开始做dfs，遇到
	 * 
	 * <pre>
	 * 1 1 0 0
	 * 1 1 1 0
	 * 0 1 1 1
	 * 0 0 1 1
	 * </pre>
	 * 
	 * @param graph
	 * @param initial
	 * @return
	 * @date 2019年4月23日
	 */
	public int minMalwareSpread(int[][] graph, int[] initial) {

		Arrays.sort(initial);

		Set<Integer> mal = new HashSet<>();

		for (int i : initial) {
			mal.add(i);
		}

		int ret = 0;

		int max = -1;

		for (int i : initial) {

			// 遍历传染源，弄到只与该传染源连接的点的数目
			Set<Integer> visited = new HashSet<>();
			visited.add(i);

			// 最上层处理不一样,
			int num = 0;

			for (int j = 0; j < graph.length; j++) {
				if (i != j && graph[i][j] == 1) {

					int dfs = dfs(j, graph, mal, visited);
					if (dfs > 0) {
						num += dfs;
					}
				}
			}

			if (num > max) {
				ret = i;
				max = num;
			}

		}

		return ret;
	}

	/**
	 * 
	 * 
	 * @param i
	 * @param graph
	 * @param mal
	 * @param visited
	 * @return
	 * @date 2019年4月24日
	 */
	private int dfs(int i, int[][] graph, Set<Integer> mal, Set<Integer> visited) {

		if (visited.contains(i)) {
			return 0;
		}

		if (mal.contains(i)) {
			return -1;
		}

		visited.add(i);

		int ret = 1;

		for (int j = 0; j < graph.length; j++) {
			if (i != j && graph[i][j] == 1) {

				int dfs = dfs(j, graph, mal, visited);

				if (dfs == -1) {
					mal.add(j);
					return -1;
				}

				ret += dfs;

			}

		}

		return ret;
	}

}
